public class Solution122 {
    public int maxProfit(int[] prices) {
        int[] f1=new int[prices.length];
        int[] f2=new int[prices.length];
        f1[0]=-prices[0];
        f2[0]=0;
        for (int i=1;i<prices.length;i++){
            f1[i]=Math.max(f1[i-1],f2[i-1]-prices[i]);
            f2[i]=Math.max(f2[i-1],f1[i-1]+prices[i]);
        }
        return f2[prices.length-1];
    }

    public static void main(String[] args) {
        System.out.println(new Solution122().maxProfit(new int[]{7,1,5,3,6,4}));
    }
}
